package main.leetcode.primary.from001to100;

import main.datastruc.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23.合并K个排序链表
 *
 * <p>合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 *
 * <p>示例: 输入: [   1->4->5,   1->3->4,   2->6 ] 输出: 1->1->2->3->4->4->5->6
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(-1);
        ListNode pre = head;
        PriorityQueue<ListNode> maxHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode listNode : lists) {
            if (listNode != null) maxHeap.offer(listNode);
        }
        ListNode node;
        while (!maxHeap.isEmpty()) {
            node = maxHeap.poll();
            pre.next = node;
            if (node.next != null) maxHeap.offer(node.next);
            pre = pre.next;
        }
        return head.next;
    }
}
